package com.zhhe.tree;

import lombok.Data;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
 *Author:ZouHeng
 *Des:二叉查找树
 *Date:2021-01-24 20:13
 */
@Data
public class BinarySearchTree<T extends Comparable<T>> {

    private Node<T> root;
    private int size;

    public BinarySearchTree() {
    }

    /**
     * 向二叉查找树中添加数据，如果该数据在二叉查找树中已经存在，则不做操作
     *
     * @param value
     */
    public void put(T value) {
        root = put(root, value);
    }

    /**
     * 因为java是值传递，所以这里必须要放回一个Node用来存储插入值后的Node
     *
     * @param node
     * @param value
     */
    public Node<T> put(Node<T> node, T value) {
        if (node == null) {
            this.size++;
            return new Node<>(null, null, value);
        }

        if (value.compareTo(node.getValue()) > 0) {
            node.setRight(put(node.getRight(), value));
        } else if (value.compareTo(node.getValue()) < 0) {
            node.setLeft(put(node.getLeft(), value));
        }
        return node;
    }

    /**
     * 删除值
     *
     * @param value
     */
    public void delete(T value) {
        root = delete(root, value);
    }

    public Node<T> delete(Node<T> node, T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getValue()) > 0) {
            node.setRight(delete(node.getRight(), value));
        } else if (value.compareTo(node.getValue()) < 0) {
            node.setLeft(delete(node.getLeft(), value));
        } else {
            //如果当前结点的左孩子结点不存在，则直接返回当前结点的右孩子结点
            if (node.getLeft() == null) {
                size--;
                return node.getRight();
            }
            //如果当前结点的右孩子结点不存在，则直接返回当前结点的左孩子结点
            if (node.getRight() == null) {
                size--;
                return node.getLeft();
            }
            //如果当前结点的左右孩子结点都存在，拿到右孩子结点中的最小值，将最小值
            //结点替换到当前结点，并将右孩子结点中的最小结点删除

            //找到最小结点
            Node<T> minNode = node.getRight();
            if (minNode.getLeft() == null) {
                //该节点的右孩子结点没有左孩子结点
                minNode.setLeft(node.getLeft());
                minNode.setRight(node.getRight().getRight());
                node = minNode;
                size--;
            } else {
                while (minNode.getLeft() != null) {
                    minNode = minNode.getLeft();
                }
                //删除右子树中的最小结点
                Node<T> delNode = node.getRight();
                while (delNode.getLeft() != null) {
                    if (delNode.getLeft().getLeft() == null) {
                        //找到了最小结点的位置，删除最小结点
                        delNode.setLeft(null);
                    } else {
                        delNode = delNode.left;
                    }
                }
                minNode.setLeft(node.getLeft());
                minNode.setRight(node.getRight());
                node = minNode;
                size--;
            }
        }
        return node;
    }

    /**
     * 获取树中的最小值
     *
     * @return
     */
    public T getMin() {
        return getMin(getMin(root)).getValue();
    }

    public Node<T> getMin(Node<T> node) {
        if (node == null) {
            return null;
        }

        if (node.getLeft() != null) {
            return getMin(node.getLeft());
        } else {
            return node;
        }
    }

    public T getMax() {
        return getMax(root).getValue();
    }

    public Node<T> getMax(Node<T> node) {
        if (node == null) {
            return null;
        }
        if (node.getRight() != null) {
            return getMax(node.getRight());
        } else {
            return node;
        }
    }

    /**
     * 二叉搜索树的前序遍历
     * 先遍历根结点，再遍历左结点，最后遍历右结点
     *
     * @return
     */
    public Queue<T> preOrder() {
        Queue<T> queue = new LinkedList<>();
        preOrder(root, queue);
        return queue;
    }

    public void preOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return;
        }
        queue.add(node.getValue());
        if (node.getLeft() != null) {
            preOrder(node.getLeft(), queue);
        }
        if (node.getRight() != null) {
            preOrder(node.getRight(), queue);
        }
        return;
    }

    /**
     * 二叉搜索树的中序遍历
     * 先遍历左结点，再遍历根结点，最后遍历右结点
     *
     * @return
     */
    public Queue<T> midOrder() {
        Queue<T> queue = new LinkedList<>();
        return midOrder(root, queue);
    }

    public Queue<T> midOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return queue;
        }

        if (node.getLeft() != null) {
            queue = midOrder(node.getLeft(), queue);
        }
        queue.add(node.getValue());
        if (node.getRight() != null) {
            queue = midOrder(node.getRight(), queue);
        }
        return queue;
    }


    /**
     * 二叉搜索树的后续遍历
     * 先遍历左结点，再遍历右结点，最后遍历根结点
     *
     * @return
     */
    public Queue<T> afterOrder() {
        Queue<T> queue = new LinkedList<>();
        return afterOrder(root, queue);
    }

    public Queue<T> afterOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return queue;
        }

        if (node.getLeft() != null) {
            queue = afterOrder(node.getLeft(), queue);
        }
        if (node.getRight() != null) {
            queue = afterOrder(node.getRight(), queue);
        }
        queue.add(node.getValue());
        return queue;
    }

    public Queue<T> layerOrder() {
        Queue<T> queue = new LinkedList<>();
        queue.add(root.getValue());
        Queue<Node<T>> layerQueue = new LinkedList<>();
        layerQueue.add(root.getLeft());
        layerQueue.add(root.getRight());
        while (!layerQueue.isEmpty()) {
            Node<T> removeNode = layerQueue.remove();
            queue.add(removeNode.getValue());
            if (removeNode.getLeft() != null) {
                layerQueue.add(removeNode.getLeft());
            }
            if (removeNode.getRight() != null) {
                layerQueue.add(removeNode.getRight());
            }
        }
        return queue;
    }

    /**
     * 获取树的最大深度
     * @return
     */
    public Integer maxDepth() {
        return maxDepth(root);
    }

    private int maxDepth(Node<T> node) {
        if (node == null) {
            return 0;
        }
        int leftMax = 0;
        int rightMax = 0;
        int max = 0;
        if (node.getLeft() != null) {
            leftMax = maxDepth(node.getLeft());
        }
        if (node.getRight() != null) {
            rightMax = maxDepth(node.getRight());
        }
        max = leftMax > rightMax ? leftMax + 1 : rightMax + 1;
        return max;
    }

    /**
     * 力扣107
     * @param root
     * @return
     */
    public List<List<T>> levelOrderBottom(Node<T> root) {
        List<List<T>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<Node<T>> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        while (!nodeQueue.isEmpty()) {
            List<T> values = new ArrayList<>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; i++) {
                Node<T> node = nodeQueue.poll();
                values.add(node.getValue());
                if (node.getLeft() != null) {
                    nodeQueue.offer(node.getLeft());
                }
                if (node.getRight() != null) {
                    nodeQueue.offer(node.getRight());
                }
            }
            list.add(0, values);
        }
        return list;
    }

    @Data
    private class Node<T> {
        private Node left;
        private Node right;
        private T value;

        public Node(Node left, Node right, T value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        tree.put(10);
        tree.put(5);
        tree.put(2);
        tree.put(8);
        tree.put(9);
        tree.put(7);
        tree.put(6);
        //        tree.delete(2);
        System.out.println(tree.getMin());
        System.out.println(tree.getMax());
    }

    @Test
    public void testOrder() {
        BinarySearchTree<String> tree = new BinarySearchTree<>();
        tree.put("E");
        tree.put("B");
        tree.put("G");
        tree.put("A");
        tree.put("D");
        tree.put("C");
        tree.put("F");
        tree.put("H");
        System.out.println("树的最大深度：" + tree.maxDepth());
        System.out.println("前序遍历");
        Queue<String> preQueue = tree.preOrder();
        for (String item : preQueue) {
            System.out.print(item + " ");
        }
        System.out.println();
        System.out.println("中序遍历");
        Queue<String> midQueue = tree.midOrder();
        for (String item : midQueue) {
            System.out.print(item + " ");
        }
        System.out.println();
        System.out.println("后序遍历");
        Queue<String> afterQueue = tree.afterOrder();
        for (String item : afterQueue) {
            System.out.print(item + " ");
        }
        System.out.println();
        System.out.println("层序遍历");
        //层序遍历顺序：E B G A D F H C
        Queue<String> layerQueue = tree.layerOrder();
        for (String item : layerQueue) {
            System.out.print(item + " ");
        }
    }



      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

      public TreeNode sortedArrayToBST(int[] nums) {
          int index = nums.length / 2;
          TreeNode root = new TreeNode(nums[index]);
          TreeNode left = root;
          for(int i = index - 1; i >= 0; i--) {
              TreeNode node = new TreeNode(nums[i]);
              left.left = node;
              left = node;
          }
          if (index < nums.length - 1) {
              TreeNode right = root;
              TreeNode node = new TreeNode(nums[nums.length - 1]);
              right.right = node;
              right = node;
              for(int i = nums.length - 2; i > index; i--) {
                  TreeNode node2 = new TreeNode(nums[i]);
                  right.left = node2;
                  left = node2;
              }
          }
          return root;
      }

      @Test
    public void testMain() {
        int[] nums = {1,3};
        TreeNode node = sortedArrayToBST(nums);
          System.out.println();
    }

}
